Let ff be a β-smooth convex function and assume we have ||𝐱∗−𝐱(1)||2≤R||\mathbf{x}^* - \mathbf{x}^{(1)}||_2 \leq R. If we run GD for TT steps, we have:

f(𝐱(T))−f(𝐱∗)≤2βR2Tf(\mathbf{x}^{(T)}) - f(\mathbf{x}^{*}) \leq \frac{2\beta R^2}{T}

Corollary

If T=O(βR2ϵ)T = O(\frac{\beta R^2}{\epsilon}) we have f(𝐱(T))−f(𝐱∗)≤ϵf(\mathbf{x}^{(T)}) - f(\mathbf{x}^{*}) \leq \epsilon

Compare to: gradient descent convergence bound, Gradient descent convergence for α-strongly convex functions